import java.util.Map;

public class project {
    public int minCut(String s) {
        int len=s.length();
        if(len<2){
            return 0;
        }
        int[] dp=new int[len];
        for(int i=0;i<len;i++){
            dp[i]=i;
        }
        for(int i=1;i<len;i++){
            if(matching(0,i,s)){
                dp[i]=0;
                continue;
            }
            for(int j=0;j<i;j++){
                if(matching(j+1,i,s)){
                    dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[len-1];
    }
    public boolean matching(int left,int right,String s){
        while (left<right){
            char chL=s.charAt(left);
            char chR=s.charAt(right);
            if(chL!=chR){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
























    public int minCut1(String s) {
        int len=s.length();
        if(len<2){
            return 0;
        }
        int[] dp=new int[len];
        for(int i=0;i<len;i++){
            dp[i]=i;
        }
        for(int i=1;i<len;i++){
            if(matching1(0,i,s)){
                dp[i]=0;
                continue;
            }
            for(int j=0;j<i;j++){
                if(matching1(j+1,i,s)){
                    dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[len-1];
    }
    public boolean matching1(int left,int right,String s){
        while (left<right){
            char chL=s.charAt(left);
            char chR=s.charAt(right);
            if(chL!=chR){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }



























    public int[][] arr;
    public int[][] direction=new int[][]{{0,1},{1,0},{-1,0},{0,-1}};
    public int longestIncreasingPath(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int ret = 0;
        arr = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                ret = Math.max(ret, dfs(i, j, matrix, row, col));
            }
        }
        return ret;
    }
    public int dfs(int x,int y,int[][] matrix,int row,int col){
        if(arr[x][y]!=0){
            return arr[x][y];
        }
        int ret=0;
        for(int i=0;i<4;i++){
            int curX=x+direction[i][0];
            int curY=y+direction[i][0];
            if(curX>=0&&curY>=0&&curX<row&&curY<col&&matrix[curX][curY]>matrix[x][y]){
                ret=Math.max(ret,dfs(curX,curY,matrix,row,col));
            }
        }
        arr[x][y]=ret+1;
        return arr[x][y];
    }





















//    public int[][] direction=new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
//    public int[][] arr;
    public int longestIncreasingPath1(int[][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        arr=new int[row][col];
        int ret=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                ret=Math.max(ret,dfs1(i,j,matrix,row,col));
            }
        }
        return ret;
    }
    public int dfs1(int x,int y,int[][] nums,int row,int col){
        if(arr[x][y]!=0){
            return arr[x][y];
        }
        int ret=0;
        for(int i=0;i<4;i++){
            int curX=x+direction[i][0];
            int curY=y+direction[i][1];
            if(curX>=0&&curY>=0&&curX<row&&curY<col&&nums[curX][curY]>nums[x][y]){
                ret=Math.max(ret,dfs1(curX,curY,nums,row,col));
            }
        }
        arr[x][y]=ret+1;
        return arr[x][y];
    }





















    public int binaryGap(int n) {
        int index=0;
        int ret=0;
        int spacing=0;
        while (n>0){
            if((n&1)==1){
                index++;
                if(index==2){
                    ret= Math.max(ret,spacing);
                    index=1;
                    spacing=1;
                }else{
                    spacing++;
                }
            }else if(index==1){
                spacing++;
            }
            n>>=1;
        }
        return ret;
    }
}
